SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Super-recursive algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Super-recursive algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Computability_theory" title="Computability theory">computability theory</a>, <b>super-recursive algorithms</b> are posited as a generalization of <a href="Hypercomputation" title="Hypercomputation">hypercomputation</a>: hypothetical <a href="Algorithm" title="Algorithm">algorithms</a> that are more powerful, that is, compute more than <a href="Turing_machines" class="mw-redirect" title="Turing machines">Turing machines</a>.

</p><p>The term was introduced by Mark Burgin, whose book <i>Super-recursive algorithms</i> develops their theory and presents several mathematical models.

</p><p>Burgin argues that super-recursive algorithms can be used to disprove the <a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a>. This point of view has been criticized within the mathematical community and is not widely accepted.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>Burgin (2005: 13) uses the term <b>recursive algorithms</b> for <a href="Algorithm" title="Algorithm">algorithms</a> that can be implemented on Turing machines, and uses the word <i>algorithm</i> in a more general sense. Then a <b>super-recursive class of algorithms</b> is "a class of algorithms in which it is possible to compute functions not computable by any <a href="Turing_machine" title="Turing machine">Turing machine</a>" (Burgin 2005: 107)

</p><p>Super-recursive algorithms are also related to <b>algorithmic schemes</b>, another novel concept from Burgin, which are more general than super-recursive algorithms. Burgin argues (2005: 115) that it is necessary to make a clear distinction between super-recursive algorithms and those algorithmic schemes that are not algorithms. Under this distinction, some types of hypercomputation are obtained by super-recursive algorithms.

</p>

<div class="mw-heading mw-heading2"><h2 id="Relation_to_the_Church–Turing_thesis">Relation to the Church–Turing thesis</h2></div>

<p>The Church–Turing thesis in recursion theory relies on a particular definition of the term <i>algorithm</i>. Based on his personal definitions that are more general than the one commonly used in recursion theory, Burgin argues that super-recursive algorithms disprove the <a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a>. He furthermore claims to prove that super-recursive algorithms could hypothetically provide even greater efficiency gains than using <a href="Quantum_algorithms" class="mw-redirect" title="Quantum algorithms">quantum algorithms</a>.

</p><p>Burgin's interpretation of super-recursive algorithms has encountered opposition in the mathematical community. One critic is logician <a href="Martin_Davis_(mathematician)" title="Martin Davis (mathematician)">Martin Davis</a>, who argues that Burgin's claims have been well understood "for decades". Davis states,

</p>

<dl><dd>"The present criticism is not about the mathematical discussion of these matters but only about the misleading claims regarding physical systems of the present and future."(Davis 2006: 128)</dd></dl>

<p>Davis disputes Burgin's claims that sets at level <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta _{2}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta _{2}^{0}}</annotation>

</semantics>

</math></span><img src="./e2647e336f34cacfba9934032137522052e8af0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.99ex; height:3.176ex;" alt="{\displaystyle \Delta _{2}^{0}}" loading="lazy"></span> of the <a href="Arithmetical_hierarchy" title="Arithmetical hierarchy">arithmetical hierarchy</a> can be called computable, saying

</p>

<dl><dd>"It is generally understood that for a computational result to be useful one must be able to at least recognize that it is indeed the result sought." (Davis 2006: 128)</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>Burgin, Mark (2005), <i>Super-recursive algorithms</i>, Monographs in computer science, Springer. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-95569-0</bdi></li>

<li>Davis, Martin (2006), "<a rel="nofollow" class="external text" href="https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf">The Church–Turing Thesis: Consensus and opposition</a>". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132</li>

<li>Peter Kugel, <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/220425557_It%27s_time_to_think_outside_the_computational_box">"It's time to think outside the computational box"</a>, <i>Communications of the ACM</i>, Volume 48, Issue 11, November 2005</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.la-acm.org/Archives/laacm9912.html">A New Paradigm for Computation</a>. Los Angeles ACM Chapter Meeting, December 1, 1999.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-02" href="https://en.wikipedia.org/wiki/?title=Super-recursive_algorithm&oldid=1260840136">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>